package leetcode;

import java.util.*;
class MaxQueue {
    public Deque<Integer> deque=null;
    public Deque<Integer> helpDeque=null;
    public MaxQueue() {
        deque=new LinkedList<>();
        helpDeque=new LinkedList<>();
    }

    public int max_value() {
        if (deque.isEmpty()){
            return -1;
        }
        return helpDeque.peek();
    }

    public void push_back(int value) {
        deque.offer(value);
        while (!helpDeque.isEmpty()&&value>helpDeque.peekLast()){
            helpDeque.pollLast();
        }
        helpDeque.offer(value);
    }

    public int pop_front() {
        if(deque.isEmpty()) {
            return -1;
        }
        int val = deque.pop();
        if(helpDeque.peek() == val) {
            helpDeque.pop();
        }
        return val;
    }
}

public class LeetCodeMain110 {

    public double[] dicesProbability(int n) {
        double[] dp=new double[6];
        Arrays.fill(dp,1.0/6.0);
        for (int i = 2; i <= n; i++) {
            double[] tmp=new double[5*i+1];
            for (int j = 0; j < dp.length; j++) {
                for (int k = 0; k < 6; k++) {
                    tmp[j+k]+=dp[j]/6.0;
                }
            }
            dp=tmp;
        }
        return dp;
    }
    public double[] value={0.16667,0.16667,0.16667,0.16667,0.16667,0.16667};
    public double[] dicesProbability1(int n) {
        if (n==1){
            return value;
        }
        double[] arr=new double[n*6-1];
        int length=arr.length;
        arr[0]=Math.pow(value[0],n);
        arr[length-1]=Math.pow(value[0],n);
        for (int i = 1; i < length-1; i++) {
            List<Integer> list=new ArrayList<>();
            List<List<Integer>> listList=new ArrayList<>();
            DFS(i+n,list,listList,0,n);
            double sum=0.0;
            for (List<Integer> list1:listList) {
                sum+=Math.pow(value[0],list1.size());
            }
            arr[i]=sum;
        }
        return arr;
    }
    public void DFS(int target,List<Integer> list,List<List<Integer>> listList,int sum,int n){
        if (sum==target&&list.size()==n){
            listList.add(new ArrayList<>(list));
            return;
        }
        for (int i = 1; i < target&&sum+i<=target; i++) {
            sum+=i;
            list.add(i);
            DFS(target, list, listList, sum, n);
            list.remove(list.size()-1);
            sum-=i;
        }
    }
    public int sumNums(int n) {
        if (n==0){
            return 0;
        }
        return n+sumNums(n-1);
    }
    public int lastRemaining1(int n, int m) {
        if (n%m==0){
            return 0;
        }
        return m;
    }
        public int lastRemaining(int n, int m) {
        int[] arr=new int[n];
        int count=0;
        int delCount=0;
        int i=0;
        while (delCount!=arr.length-1){
            if (arr[i]!=-1){
                if (count!=m){
                    count++;
                }
                if (count==m){
                    delCount++;
                    arr[i]=-1;
                    count=0;
                }
            }
            i=(i+1)%n;
        }
        for (int j = 0; j < n; j++) {
            if (arr[j]==0){
                return j;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
//        Scanner in=new Scanner(System.in);
//        int n=in.nextInt();
//        int m=in.nextInt();
//        LeetCodeMain110 main110=new LeetCodeMain110();
//        System.out.println(main110.lastRemaining(n,m));
//        Queue<Integer> queue=new LinkedList<>();
//        queue.offer(0);
//        queue.offer(1);
//        queue.offer(2);
//        System.out.println(queue.poll());
        Deque<Integer> deque=new LinkedList<>();
//        deque.offer(1);
//        deque.offer(2);
//        deque.offer(3);
//        deque.offer(4);
//        deque.offer(5);
        deque.offerFirst(1);
        deque.offerFirst(2);
        System.out.println(deque.pollLast());
    }
}
